#include <stdio.h>
#include <stdlib.h>

#define SIZE 9

typedef struct Element {
    int key;
} *Element;

typedef struct HashTable {
    Element *table;
} *HashTable;

void init(HashTable hashTable) {
    hashTable->table = (Element *) malloc(sizeof(struct Element) * SIZE);
    for (int i = 0; i < SIZE; ++i) {
        hashTable->table[i] = NULL;
    }
}

int hash(int key) {  //哈希函数
    return key % SIZE;
}

void insert(HashTable hashTable, Element element) {   //插入操作，注意没考虑满的情况，各位小伙伴可以自己实现一下
    int hashCode = hash(element->key), count = 0;
    while (hashTable->table[hashCode]) {   //如果发现哈希冲突，那么需要继续寻找
        hashCode = hash(element->key + (++count));
    }
    hashTable->table[hashCode] = element;   //对号入座
}

_Bool find(HashTable hashTable, int key) {
    int hashCode = hash(key), count = 0;   //首先计算元素的哈希值
    const int startIndex = hashCode;   //记录一下起始位置，要是转一圈回来了得停
    do {
        if (hashTable->table[hashCode]->key == key) return 1;  //如果找到就返回1
        hashCode = hash(key + ++count);
    } while (startIndex != hashCode && hashTable->table[hashCode]);  //没找到继续找
    return 0;
}

Element create(int key) {    //创建一个新的元素
    Element element = (Element) malloc(sizeof(struct Element));
    element->key = key;
    return element;
}

int main() {
    struct HashTable hashTable;
    init(&hashTable);
//    insert(&hashTable, create(9));
//    insert(&hashTable, create(7));
//    insert(&hashTable, create(13));
//    insert(&hashTable, create(29));
    for (int i = 0; i < 9; ++i) {
        insert(&hashTable, create(i * 9));
    }

    for (int i = 0; i < 9; ++i) {
        printf("%d ", hashTable.table[i]->key);
    }
    printf("\n");
    for (int i = 0; i < SIZE; ++i) {
        if (hashTable.table[i]) {
            printf("%d ", hashTable.table[i]->key);
        } else {
            printf("NULL ");
        }
    }
//    printf("%d\n", find(&hashTable, 1));
//    printf("%d\n", find(&hashTable, 13));
    return 0;
}